Graph Theory
Table of Contents
1. Graph
1.1. Definitions
- \(G=(V, E)\) A set of vertices and a set of edges connecting two vertices.
- \(|G|\) is the number of vertices in a graph \(G\).
- \(G_2
- \(\partial G_2\) is boundary of \(G_2\), which is a set of edge that is connected to \(V_2\) but not in \(E_2\).
- \(h(G_2)\) is expansion rate of \(G_2\) defined as \[ h(G_2)=\frac{|\partial G_2|}{\min(|G_2|, |G_2^C|)}. \]
1.2. Best Possible Expander Graph1
- For the measure of well-connectedness we use the the minimum of expansion rates of subgraphs.
- Lower bound of expansion rate for \(d\)-regular graph is given by Cheeger inequality and Alon-Boppana bound. \[ h(G_2)\ge \frac{1}{2}(d-\lambda_2),\ \ \ \ \lambda_2 \ge 2\sqrt{d-1}-\alpha \] where \(d\) is the degree of a graph which is also the first eigenvalue of its adjacency matrix, and \(\lambda_2\) is the second eigenvalue.
- Low \(\lambda_2\) can be achieved with high probability using random \(n\) cycles.
2. Tree
- An acyclic graph is an unrooted tree, in which case the leaves are the nodes with degree one.
- The root of a tree can be chosen.
2.1. Binary Tree
2.1.1. Heap
- In a max-heap (or min-heap), two child nodes are less than (or greater than) the parent.
- ((65dc61b0-e3ab-49be-9b51-aa1acde0e5eb))
2.1.2. Binary Search Tree
- The left child is less than the parent, and the right child is greater than the parent.
3. Graph Traversal
3.1. Path
- Sequence of vertices with edges between them, where all vertices are distinct.
3.2. Cycle
- Path that starts and ends on the same vertex.
3.3. Trail
- Sequence of vertices with edges between them, where all edges are distinct.
3.4. Circuit
- Trail that starts and ends on the same vertex.
3.5. Euler Trail
- aka Euler Path
- Trail that includes every edges.
3.6. Euler Circuit
- Euler Trail that starts and ends on the same vertex.
4. Adjacency Matrix
- A matrix that represents the graph efficiently.
- For a undirected graph, the adjacency matrix is symmetric.
- Adjacency List, which is an array of list of vertices that are connected, is also available.
- \(a_{ij} = 1\) if \((n_i, n_j) \in E\).
5. Incidence Matrix
- For a directed graph,
- \[ b_{ik} = \begin{cases} 1, & \text{edge $k$ points towards node $i$},\\ -1, & \text{edge $k$ leaves node $i$},\\ 0, &\text{otherwise}. \end{cases} \]
- It is the linear map from the vector space generated by edges, to
the vector space generated by vertices.
- e.g. \(B(e_1 = (n_1, n_2)) = n_2 - n_1\).
- The elements of the null space are the cycles.
- Circuits, Graph Theory, and Linear Algebra | #some2 - YouTube
- Daniel Spielman “Miracles of Algebraic Graph Theory” - YouTube
6. Reference
- The Beauty of Graph Theory. Chapter 1 | The Beauty of Graph Theory - YouTube
Footnotes:
1
Math behind SoME3. https://youtu.be/XSDBbCaO-kc.